#include <stdio.h>
void Swap(int *dest,int* src)//交换
{
    int tmp =*dest;
   *dest=*src;
   *src= tmp;
}
void AdjustDown(int *arr,int tmp,int father)//👇调整，他的俩个儿子节点一定要是小堆or大堆
{
    int son= father*2+1;//右孩子
    while(son<tmp)
    {
        if(son+1<tmp&&arr[son+1]>arr[son])//找左右孩子中最小的那个,且可以这个节点只有一个孩子
        {
            ++son;
        }
        if(arr[son]>arr[father])
        {
            Swap(&arr[father],&arr[son]);
            father=son;
            son=father*2+1;
        }
        else
        {
            break;
        }

    }
}


void HeapSort(int *a,int n)//堆排序
{
    for(int i=(n-1-1)/2;i>=0;--i)//建立大堆or下堆
    {
        AdjustDown(a,n,i);
    }

    int end=n-1;
   while(end>0)
   {
       Swap(&a[0],&a[end]);
       AdjustDown(a,end,0);
       end--;
   }

}

int main()
{

    int arr[]={12,30,22,88,60,79,33,8,10,99,};
    //int arr[]={15,18,28,25,19,34,65,27,49,31};
    int sz=sizeof(arr)/sizeof (arr[0]);
    //AdjustDown(arr,sz,0);
    HeapSort(arr,sz);
    return 0;
}

void AdjustUp(int *arr,int tmp,int son)//👆调整
{
    int father= (son-2)/2;
    while(son>0)
    {
        if(arr[father]>arr[son])
        {
            Swap(&arr[father],&arr[son]);
            son=father;
            father=(son-1)/2;
        }
        else
        {
            break;
        }
    }
}
